package Solution.problem092.ReverseLinkedList2;

import common.ListNode;
import org.junit.Test;

/**
 * @program Leetcode
 * @description:
 *
 * Reverse a linked list from position m to n. Do it in-place and in one-pass.
 *
 * For example:
 * Given 1->2->3->4->5->NULL, m = 2 and n = 4,
 *
 * return 1->4->3->2->5->NULL.
 *
 * Note:
 * Given m, n satisfy the following condition:
 * 1 ≤ m ≤ n ≤ length of list.

 *思路：
 *  遍历链表，抽离需要翻转部分链表进行发转操作
 *  头拼接与尾拼接
 *  主要考察链表操作
 * @author: lishangsheng
 * @create: 2019/07/01 14:48
 */
public class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        if (head == null || head.next == null || m == n) {
            return head;
        }
        ListNode normal = head, last = null, pre, cur, gra = new ListNode(0);
        gra.next = head;
        pre = gra;
        cur = head;
        while (cur != null) {
            if (m == 1) {
                normal = cur;
                // 链表反转,头拼接
                last = reverseList(cur, pre, n);
                // 尾拼接
                normal.next = last;
                break;
            }
            //先找到要开始反转到地方
            cur = cur.next;
            pre = pre.next;
            m--;
            n--;
        }
        return gra.next;
    }

    // 反转链表工具方法,反转当前节点与之后n个节点的子链表,头拼接
    public ListNode reverseList(ListNode head, ListNode first, int n) {
        ListNode pre = null;
        ListNode next = head;
        while (n > 0) {
            ListNode tmp = next.next;
            next.next = pre;
            pre = next;
            next = tmp;
            n--;
        }
        first.next = pre;
        return next;
    }

    @Test
    public void test() {
        //1->2->3->4->5
        ListNode listNode1 = new ListNode(0);
        ListNode listNode2 = new ListNode(1);
        ListNode listNode3 = new ListNode(2);
        ListNode listNode4 = new ListNode(3);
        ListNode listNode5 = new ListNode(4);
        listNode1.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = listNode4;
        listNode4.next = listNode5;

        ListNode result = reverseBetween(listNode1, 2, 4);
        System.out.println(result.val);
    }
}
